package leecode;
/**
 * 题目：主要元素
 * 题目描述： 数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
 * 细节：超过一半，即一半的元素都是这个，不是大于一半元素的意思
 */
class Solution_1710 {
    public static int majorityElement(int[] nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            // 两个数抵消完了
            if (count == 0) {
                candidate = num;
            }
            // 碰到相同的数字
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        count = 0;
        int length = nums.length;

        // 计算上面得到的candidate出现次数
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        return count * 2 > length ? candidate : -1;
    }

    public static void main(String[] args) {
        // java中所有对象都应该使用new建立，python可以直接赋值
        int[] nums_1 = new int[]{1,2,5,9,5,9,5,5,5};
        int[] nums_2 = new int[]{2,3};
        System.out.println(majorityElement(nums_1));
        System.out.println(majorityElement(nums_2));
        
    }

}

/**
    由于时间复杂度要求和空间复杂度要求，符合条件的的只有Boyer-Moore投票算法
    两个队伍极限一换一
    Boyer-Moore投票算法基本思想：在每一轮投票过程中，从数组中删除两个不同的元素，直到投票过程无法继续，
此时数组为空或者数组中剩下的元素都相等。
    1.如果数组为空，则数组中不存在主要元素；
    2.如果数组中剩下的元素都相等，则数组中剩下的元素可能为主要元素。

    Boyer-Moore投票算法步骤：
    1.维护一个候选主要元素candidate 和候选主要元素的出现次数count，初始时candidate为任意值，count=0；
    2.遍历数组nums中的所有元素，遍历到x时候，进行如下操作：
        2.1 若count==0，将x的值赋给candidate，否则不更新candidate；
        2.2 若x==candidate，则count+1，否则count-1；
    3.遍历结束之后，若nums中存在主要元素，则candidate为主要元素，否则candidate可能为数组中任意元素
    由于不一定存在主要元素，因此需要第二次遍历数组，验证 candidate 是否为主要元素。
    第二次遍历时，统计candidate在数组中的出现次数，如果出现次数大于数组长度的一半，则 candidate 是主要元素，
    返回candidate，否则数组中不存在主要元素，返回 -1。

    在Boyer-Moore 投票算法中，遇到相同的数则将count加1，遇到不同的数则将count减1。根据主要元素的定义，
    主要元素的出现次数大于其他元素的出现次数之和，因此在遍历过程中，主要元素和其他元素两两抵消，最后一定
    剩下至少一个主要元素，此时candidate 为主要元素，且count≥1。

*/